﻿#include <iostream>
#include <assert.h>
#include <string>
#include <stack>
#include <deque>

using namespace std;

#define NUMSTR_SIZE 24

/**
 * 查看栈中的顶部是否是乘号或除号，如果是，需要先取出栈顶的2个元素，与接下来的数字进行结算
 */
static bool calcMulOrDiv(stack<string>& strStack, int& extraNum)
{
	bool isTopMulOrDiv = false;
	string top;
	char operation = '\0';
	char numStr[NUMSTR_SIZE] = { 0 };
	int num2;

	if (strStack.size() > 1)
	{
		top = strStack.top();
		operation = top.at(0);
		if (operation == '*' || operation == '/')
		{
			isTopMulOrDiv = true;
			num2 = extraNum;
			strStack.pop();
			top = strStack.top();
			strStack.pop();
			sscanf_s(top.c_str(), "%d", &extraNum);
			if (operation == '*')
			{
				extraNum *= num2;
			}
			else if (operation == '/')
			{
				extraNum /= num2;
			}

			memset(numStr, 0, NUMSTR_SIZE);
			sprintf_s(numStr, "%d", extraNum);
			strStack.push(numStr);
			extraNum = 0;
		}
	}

	return isTopMulOrDiv;
}

typedef struct
{
	int result;
	int curIndex;
}FunctionStringReturnData;

/**
 * 如果有括号，则进行递归
 */
static FunctionStringReturnData calc(const char* str, const int startIndex)
{
	FunctionStringReturnData data;
	FunctionStringReturnData childData;
	size_t strSize = strlen(str);
	int num = 0;
	bool isNumValid = false;
	int index = startIndex;
	stack<string> strStack;
	char cur;
	char numStr[NUMSTR_SIZE] = { 0 };

	while (index < strSize)
	{
		cur = str[index];
		switch (cur)
		{
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
		case ')':
			if (cur != ')')
			{
				num = num * 10 + cur - '0';
				isNumValid = true;
			}

			if (index == strSize - 1 || cur == ')')
			{
				if (isNumValid && !calcMulOrDiv(strStack, num))
				{
					memset(numStr, 0, NUMSTR_SIZE);
					sprintf_s(numStr, "%d", num);
					strStack.push(numStr);
					isNumValid = false;
				}
			}
			break;

		case '+':
		case '-':
		case '*':
		case '/':
			if (isNumValid && !calcMulOrDiv(strStack, num))
			{
				memset(numStr, 0, NUMSTR_SIZE);
				sprintf_s(numStr, "%d", num);
				strStack.push(numStr);
				isNumValid = false;
			}
			
			memset(numStr, 0, NUMSTR_SIZE);
			numStr[0] = cur;
			strStack.push(numStr);
			num = 0;
			break;

		case '(':
			childData = calc(str, index + 1);
			index = childData.curIndex;
			num = childData.result;
			if (!calcMulOrDiv(strStack, num))
			{
				memset(numStr, 0, NUMSTR_SIZE);
				sprintf_s(numStr, "%d", num);
				strStack.push(numStr);
			}

			isNumValid = false;
			break;
		}

		if (cur == ')')
			break;

		++index;
	}

	data.curIndex = index;

	stack<string> resStack;
	string top;
	while (!strStack.empty())
	{
		top = strStack.top();
		strStack.pop();
		resStack.push(top);
	}

	index = 0;
	num = 0;
	int num2;
	char operation = '\0';

	while (!resStack.empty())
	{
		top = resStack.top();
		resStack.pop();

		if (top.at(0) == '-' || top.at(0) == '+')
		{
			operation = top.at(0);
		}
		else
		{
			if (index == 0)
			{
				sscanf_s(top.c_str(), "%d", &num);
			}
			else
			{
				sscanf_s(top.c_str(), "%d", &num2);
				if (operation == '+')
				{
					num += num2;
				}
				else if (operation == '-')
				{
					num -= num2;
				}
				else
				{
					assert(false && "invalid operation");
				}
			}
		}

		++index;
	}

	data.result = num;
	return data;
}

#define TMPSTR_SIZE 100

/**
 * 左神的方法
 */
static void addNum(deque<string>& que, int num)
{
	if (!que.empty())
	{
		int cur = 0;
		string top = que.back();
		que.pop_back();
		if (top == "+" || top == "-")
		{
			que.push_back(top);
		}
		else
		{
			string top2 = que.back();
			que.pop_back();
			sscanf_s(top2.c_str(), "%d", &cur);
			num = top == "*" ? (cur * num) : (cur / num);
		}
	}

	char tmpStr[TMPSTR_SIZE] = { 0 };
	sprintf_s(tmpStr, "%d", num);
	que.push_back(tmpStr);
}

/**
 * 左神的方法
 */
static int getNum(deque<string>& que)
{
	int res = 0;
	bool add = true;
	string cur;
	int num = 0;

	while (!que.empty())
	{
		cur = que.front();
		que.pop_front();
		if (cur == "+")
		{
			add = true;
		}
		else if (cur == "-")
		{
			add = false;
		}
		else
		{
			sscanf_s(cur.c_str(), "%d", &num);
			res += add ? num : (-num);
		}
	}

	return res;
}

/**
 * 左神的方法
 * 请从str[i...]往下算，遇到字符串终止位置或者右括号，就停止
 */
static FunctionStringReturnData value(const char* str, int i)
{
	deque<string> que;
	int num = 0;
	FunctionStringReturnData bra;
	memset(&bra, 0, sizeof(FunctionStringReturnData));
	auto strLength = strlen(str);
	char tmpStr[TMPSTR_SIZE];

	while (i < strLength && str[i] != ')')
	{
		if (str[i] >= '0' && str[i] <= '9')
		{
			num = num * 10 + str[i++] - '0';
		}
		else if (str[i] != '(')
		{
			// 遇到的是运算符
			addNum(que, num);
			memset(tmpStr, 0, TMPSTR_SIZE);
			tmpStr[0] = str[i++];
			que.push_back(tmpStr);
			num = 0;
		}
		else
		{
			// 遇到左括号了
			bra = value(str, i + 1);
			num = bra.result;
			i = bra.curIndex + 1;
		}
	}

	addNum(que, num);

	bra.result = getNum(que);
	bra.curIndex = i;
	return bra;
}

/**
 * 给定一个字符串str，str表示一个公式，公式中可能有整数、加减乘除符号和左右括号，返回公式的计算结果。
 * 举例：
 * str="48*((70-65)-43)+8*1", 返回-1816
 * str="3+1*4", 返回7
 * str="3+(1*4)", 返回7
 * 说明：
 * 1. 可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
 * 2. 如果是负数，就需要用括号括起来，比如"4*(-3)"。但是如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。
 * 3. 不用考虑计算过程中会发生溢出的情况。
 * 
 * 思路：
 * 首先考虑没有括号的情况。
 * 没有括号的情况，从左到右依次处理数字和符号，利用1个string栈来缓存信息。
 * 在读取数字的时候，逐个解析字符，直到出现了符号或者字符串结尾，先不着急将数字存入栈中，而是将数字存到一个局部变量num中。当读取到一个运算符，需要先看下栈顶是否×或÷，如果是的话，从栈中取出栈顶的2个元素，直接与num作运算，再将运算之后的数字存入栈；如果不是×或÷，则先将num存入栈，再将运算符存入栈。最后，将栈中的元素按照从底部到顶部的顺序，依次计算得到最终的计算结果。
 * 
 * 然后考虑有括号的情况。
 * 假设没有括号的处理方式定义为func(), 还是从左到右依次处理字符，如果读取到'(', 则从'('的下一个位置调用func(), func()内部，如果读取到'('，再调用func()...; func()中，如果读取到')', 则结算结果返回到上一级调用处。
 */
int main_functionString()
{
	char functionStr[] = "3*(5*3+4*2*(1+2*3))+6*(8+3)";
	auto res = calc(functionStr, 0);
	auto res2 = value(functionStr, 0);
	auto realRes = 3 * (5 * 3 + 4 * 2 * (1 + 2 * 3)) + 6 * (8 + 3);
	printf("res=%d, res2=%d, real=%d\n", res.result, res2.result, realRes);
	return 0;
}